import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/*
 * @lc app=leetcode.cn id=1584 lang=java
 *
 * [1584] 连接所有点的最小费用
 */

// @lc code=start
class Solution {
    // prim或者kruskal算法都可以，这是一个最小生成树的问题
    // 这里使用kruskal，用并查集，理论上时间复杂度O(ElogE)，适合求解稀疏图
    public int minCostConnectPoints(int[][] points) {
        List<Edge> edges= new ArrayList<>();
        int len = points.length;
        for(int i = 0 ; i<len ;i++){
            for(int j=i+1;j<len;j++){//任意两点之间形成的边
                edges.add(new Edge(countDist(points,i, j), i, j));
            }
        }
        Collections.sort(edges,(e1,e2)->e1.dist-e2.dist);//由小到大排序，这样子遍历的时候就是从小到大加入的了
        // Collections.sort(edges, new Comparator<Edge>() {
        //     public int compare(Edge edge1, Edge edge2) {
        //         return edge1.dist - edge2.dist;
        //     }
        // });
        int ans = 0,num=1;//ans记录路径和，num记录使用了的点,一开始为1，可以这么理解：第一次会加入两个点进来，后面每次加入一个点。
        UnionFind uf = new UnionFind(len);
        for(var edge: edges){
            int x = edge.x, y=edge.y ,dist = edge.dist;
            if(uf.union(x, y)){//说明不在一个连通图
                ans+=dist;
                num++;
                if(num == len) break;//直到所有的点被加入即停止。
            }
        }
        return ans;
    }

    public int countDist(int[][] points,int x, int y){
        return Math.abs(points[x][0]-points[y][0])+Math.abs(points[x][1]-points[y][1]);
    }

    class UnionFind{
        int[] parent;

        public UnionFind(int n){
            parent = new int[n];
            for(int i =0;i<n;i++){
                parent[i]=i;//指向自己
            }
        }

        public int find(int x){
            return parent[x]==x? x:(parent[x]=find(parent[x]));//路径压缩
        }

        public boolean union(int x,int y){//有返回值的，如果在同一个连通分量内要返回false
            int parentX=find(x);
            int parentY=find(y);
            if(parentX==parentY) return false;

            parent[parentY]=parentX;//让y的根指向x的根
            return true;
        }
    }

    class Edge{
        int dist,x,y;//dist代表曼哈顿距离
        public Edge(int dist,int x ,int y ){
            this.dist=dist;
            this.x = x;
            this.y = y;
        }

    }
}
// @lc code=end

